package leetcode.dp;

import java.util.Arrays;
import java.util.stream.IntStream;

public class MinimumFallingPathSumII1289 {
    public static void main(String[] args) {
        new MinimumFallingPathSumII1289().new Solution2().minFallingPathSum(new int[][]{
                {1,2,3},
                {4,5,6},
                {7,8,9}
        });
    }
    class Solution1 {
        public int minFallingPathSum(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0] == null ||grid[0].length == 0) {
                return 0;
            }
            int n = grid.length;
            int[][] dp = new int[n][n];
            dp[0] = Arrays.copyOf(grid[0], n);
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i][j] = grid[i][j] + preMin(dp[i - 1], j);
                }
            }
            return IntStream.of(dp[n - 1]).min().getAsInt();
        }

        public int preMin(int arr[], int j) {
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < arr.length; i++) {
                if (i != j) {
                    min = Math.min(min, arr[i]);
                }
            }
            return min;
        }
    }

    class Solution2 {
        public int minFallingPathSum(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
                return 0;
            }
            int n = grid.length;
            int[][] dp = new int[n][n];
            int index1 = -1;
            int index2 = -1;
            for (int i = 0; i < n; i++) {
                dp[0][i] = grid[0][i];
                if (dp[0][i] < (index1 == -1 ? Integer.MAX_VALUE : dp[0][index1])) {
                    index2 = index1;
                    index1 = i;
                } else if (dp[0][i] < (index2 == -1 ? Integer.MAX_VALUE : dp[0][index2])) {
                    index2 = i;
                }
            }
            for (int i = 1; i < n; i++) {
                int tempIndex1 = -1;
                int tempIndex2 = -1;
                for (int j = 0; j < n; j++) {
                    if (j != index1) {
                        dp[i][j] = grid[i][j] + dp[i - 1][index1];
                    } else {
                        dp[i][j] = grid[i][j] + dp[i - 1][index2];
                    }
                    if (dp[i][j] < (tempIndex1 == -1 ? Integer.MAX_VALUE : dp[i][tempIndex1])) {
                        tempIndex2 = tempIndex1;
                        tempIndex1 = j;
                    } else if (dp[i][j] < (tempIndex2 == -1 ? Integer.MAX_VALUE : dp[i][tempIndex2])) {
                        tempIndex2 = j;
                    }
                }
                index1 = tempIndex1;
                index2 = tempIndex2;
            }
            return dp[n - 1][index1];
        }
    }

    class Solution3 {
        public int minFallingPathSum(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
                return 0;
            }
            int n = grid.length;
            int[][] dp = new int[2][n];
            int index1 = -1;
            int index2 = -1;
            for (int i = 0; i < n; i++) {
                dp[0][i] = grid[0][i];
                if (dp[0][i] < (index1 == -1 ? Integer.MAX_VALUE : dp[0][index1])) {
                    index2 = index1;
                    index1 = i;
                } else if (dp[0][i] < (index2 == -1 ? Integer.MAX_VALUE : dp[0][index2])) {
                    index2 = i;
                }
            }
            for (int i = 1; i < n; i++) {
                int tempIndex1 = -1;
                int tempIndex2 = -1;
                for (int j = 0; j < n; j++) {
                    if (j != index1) {
                        dp[i & 1][j] = dp[(i - 1) & 1][index1] + grid[i][j];
                    } else {
                        dp[i & 1][j] = dp[(i - 1) & 1][index2] + grid[i][j];
                    }
                    if (dp[i & 1][j] < (tempIndex1 == -1 ? Integer.MAX_VALUE : dp[i & 1][tempIndex1])) {
                        tempIndex2 = tempIndex1;
                        tempIndex1 = j;
                    } else if (dp[i & 1][j] < (tempIndex2 == -1 ? Integer.MAX_VALUE : dp[i & 1][tempIndex2])) {
                        tempIndex2 = j;
                    }
                }
                index1 = tempIndex1;
                index2 = tempIndex2;
            }
            return dp[(n - 1) & 1][index1];
        }
    }

    class Solution4 {
        public int minFallingPathSum(int[][] grid) {
            if (grid == null || grid[0].length == 0 || grid[0] == null || grid[0].length == 0) {
                return 0;
            }
            int n = grid.length;
            int[][] dp = new int[2][n];
            int index1 = -1;
            int index2 = -1;
            for (int i = 0; i < n; i++) {
                dp[0][i] = grid[0][i];
                if (dp[0][i] < (index1 == -1 ? Integer.MAX_VALUE : dp[0][index1])) {
                    index2 = index1;
                    index1 = i;
                } else if (dp[0][i] < (index2 == -1 ? Integer.MAX_VALUE : dp[0][index2])) {
                    index2 = i;
                }
            }
            for (int i = 1; i < n; i++) {
                int tempIndex1 = -1;
                int tempIndex2 = -1;
                for (int j = 0; j < n; j++) {
                    if (j != index1) {
                        dp[i & 1][j] = grid[i][j] + dp[(i - 1) & 1][index1];
                    } else {
                        dp[i & 1][j] = grid[i][j] + dp[(i - 1) & 1][index2];
                    }
                    if (dp[i & 1][j] < (tempIndex1 == -1 ? Integer.MAX_VALUE : dp[i & 1][tempIndex1])) {
                        tempIndex2 = tempIndex1;
                        tempIndex1 = j;
                    } else if (dp[i & 1][j] < (tempIndex2 == -1 ? Integer.MAX_VALUE : dp[i & 1][tempIndex2])) {
                        tempIndex2 = j;
                    }
                }
                index1 = tempIndex1;
                index2 = tempIndex2;
            }
            return dp[(n - 1) & 1][index1];
        }
    }
}
